数位DP 同类分布

发表于 | 评论数： | 阅读次数：

今天真是 开心又充实 的一天啊~~~

DP虐我千百遍，我待DP如初恋（**）

同类分布：https://www.luogu.org/problemnew/show/P4127

一眼数位DP （废话

还是按照模板分成两部分，$f[i][j][k]$ 表示确定了i位数，和为j，余数为k，然后枚举Mod即可

$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
#define int long long
int len,Mod,a[21],A,B,f[20][200][200];
int dfs(int p,int s,int x,int limit)
{
	if(p>len)
	{
		if(x==0&&Mod==s)return 1;
		return 0;
	}
	if(!limit&&f[p][s][x]!=-1)return f[p][s][x];
	int up=9,res=0;
	if(limit)up=a[len-p+1];
	for(int i=0;i<=up;i++)
		res+=dfs(p+1,s+i,(10*x+i)%Mod,limit&&(i==up));
	if(limit)return res;
	else return f[p][s][x]=res;
}
int solve(int x)
{
	len=0;
	int res=0;
	while(x)
	{
		a[++len]=x%10;
		x/=10;
	}
	for(Mod=1;Mod<=len*9;Mod++)
	{
		memset(f,-1,sizeof(f));
		res+=dfs(1,0,0,1);
	}
	return res;
}
signed main()
{
	scanf("%lld%lld",&A,&B);
	printf("%lld\n",solve(B)-solve(A-1));
}

撒fafa~